package two.divide;

/**
 * 实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）
 */
public class MyPow {
    /**
     暴力：循环 时间复杂度：O(n）
     */
    // public double myPow(double x, int n) {
    //     double ans = 1;
    //     if(n < 0){
    //         for(int i = 0; i < -n; i++){
    //             ans = ans * 1 / x;
    //         }
    //     }
    //     if(n == 0) return 1;
    //     for(int i = 0; i < n; i++){
    //         ans = ans * x;
    //     }
    //     return ans;
    // }

    /**
     分治算法：O(logn)
     */
    public double myPow(double x, long n) {
        if(n < 0) return 1 / myPow(x, -n);
        if(n == 0) return 1;
        double temp = myPow(x, n / 2);
        if(n % 2 == 0){
            return temp * temp;
        }else{
            return temp * temp * x;
        }
    }
}
